package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 归并排序 <br>
 * <pre>
 *     两路归并
 * </pre>
 *
 * @author zengjian
 * @create 2018-06-25 17:23
 * @since 1.0.0
 */
public class MergeSorter implements Sorter {
    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        int[] arrTemp = new int[arr.length];
        mergeSort(arr, arrTemp, 0, length);
    }

    private void mergeSort(int[] arr, int[] arrTemp, int lower, int higher) {
        if (lower < higher) {
            int middle = (higher - lower) / 2;
            mergeSort(arr, arrTemp, 0, lower);
            mergeSort(arr, arrTemp, middle + 1, higher);
            merge(arr, arrTemp, lower, middle, higher);
        }

    }

    private void merge(int[] arr, int[] arrTemp, int lower, int middle, int higher) {
        int start1 = lower;
        int start2 = middle;

        int cusor = -1;

        //开始归并取值
        for (; ; ) {
            if (start1 >= middle && start2 >= higher) {
                break;
            }
            if (arr[start1] <= arr[start2]) {
                arrTemp[++cusor] = arr[start1];
                start1++;
            } else if (arr[start1] > arr[start2]) {
                arrTemp[++cusor] = arr[start2];
                start2++;
            } else {
                // ==的情况默认采用1
            }
        }

        for (int i = higher; i >= lower; i++) {
            arr[higher] = arrTemp[cusor--];
        }
    }
}
